package _11_整理题目._2_二叉树_递归_dfs_bfs._递归;

import org.junit.Test;
import util.TreeNode;

import java.util.Stack;

/**
 * https://leetcode-cn.com/problems/validate-binary-search-tree/
 *
 * 搜索二叉树：
 *      1、左子树节点值都小于 根节点，右子树值都大于 根节点
 *          递归输入参数：root, lower, upper
 *          递归结束条件：root == null
 *          递归判断逻辑：root.va 是否在 给定的 lower, upper 区间之内
 *              如果不在，返回 false
 *              如果在，继续递归 左子节点并更新upper，递归右子节点并更新lower
 *      2、中序遍历结果是升序的 // 比递归要慢一下，但 复杂度一样
 *          用一个 preValue 记录下前一个值
 *          当前 root.val 如果小于等于 return false
 */
public class _03_判断二叉树是否是搜索二叉树 {

    public boolean isValidBST(TreeNode root) {
        return recursion(root, Long.MIN_VALUE, Long.MAX_VALUE);
    }

    public boolean recursion(TreeNode root, long lower, long upper) {
        if (root==null) return true;

        if (root.val <= lower || root.val >= upper) return false;

        return recursion(root.left, lower, root.val) && recursion(root.right, root.val, upper);
    }

    @Test
    public void main() {
        Integer[] integers = {1, 5, null, null, 3, 6};
        TreeNode root = TreeNode.getTreeFromArray(integers);
        System.out.println(isValidBST(root));
    }

    public boolean isValidBST1(TreeNode root) {
        Stack<TreeNode> stack = new Stack<>();
        long preValue = Long.MIN_VALUE;
        while (root!=null || !stack.isEmpty()) {
            while (root!=null) {
                stack.push(root);
                root = root.left;
            }
            root = stack.pop();

            if (root.val <= preValue) return false;
            preValue = root.val;

            root = root.right;
        }
        return true;
    }

}
